package com.cf.r1043_d;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class c2 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            solve();
        }
        out.flush();
        out.close();
        br.close();
    }

    static void solve() throws IOException {
        String[] s = br.readLine().split(" ");
        long n = Long.parseLong(s[0]);
        long k = Long.parseLong(s[1]);
        long[] num = new long[21];
        long ans = 0L, sum = 0L;
        for (int bit = 20; bit >= 0; bit--) {
            long p = (long) Math.pow(3, bit);
            if (n >= p) {
                long cnt = n / p;
                num[bit] += cnt;
                sum += cnt;
                n -= p * cnt;
            }
        }
        if (sum > k) {
            out.println(-1);
            return;
        }
        else {
            for (int bit = 20; bit >= 1; bit--) {
                long now = (k - sum) / 2;
                if (now == 0) break;
                if (now >= num[bit]) {
                    num[bit - 1] += num[bit] * 3;
                    sum += num[bit] * 2;
                    num[bit] = 0;
                } else {
                    num[bit - 1] += now * 3;
                    num[bit] -= now;
                    sum += now * 2;
                }
            }
        }
        for (int bit = 20; bit >= 0; bit--) {
            ans += pir(bit) * num[bit];
        }
        out.println(ans);
    }

    public static long pir(int x) {
        if (x == 0) return 3;
        return (long) (Math.pow(3, x + 1) + x * Math.pow(3, x - 1));
    }

}
